1. Field of the Invention
This invention relates generally to a signal processing method and apparatus for fusing a plurality of signals corresponding to estimates of the state of an object, system, or process. The method and apparatus is specialized or programmed for (1) receiving estimates, each of which can be expressed in the form of a state vector and an error matrix, and (2) transmitting a resulting signal corresponding to an estimate, which can be expressed in the form of a state vector and an error matrix, in order to evoke a physical response from a system receiving the signal.
2. Discussion of Background and Prior Art
The Data Fusion Signal Processing Problem:
The data fusion problem is essentially one of producing a single estimate of the state of an object, system, or process that combines information from multiple estimates related to the state of that object, system, or process. A typical physical example of a data fusion system is a tracking filter that maintains an estimate of the position, speed, and bearing of an autonomous vehicle and must fuse that estimate with estimate signals obtained from physical sensors, which measure quantities related to the state of the vehicle, in order to produce a single improved estimate signal that can be used by a controlling device to precisely steer the vehicle.
A signal herein is defined as any measurable quantity that is related to the changing of the physical state of a process, system, or substance. A signal includes, but is not limited to, radiation produced by a natural or man made process, electrical fluctuations produced by a natural or a man made process, distinctive materials or chemicals produced by a natural or man made process, distinctive structures or configurations of materials produced by a natural or man made process, or distinctive patterns of radiation or electrical activity produced by a natural or a man made process.
Most generally, a signal representing a measurement of any physical system inherently has some degree of random error associated therewith. Thus, the model of any physical system, if it is to accurately account for that random error, must include a way to estimate the expected values and uncertainties in the values of the physical system that occur due to the random error. Some methods assume that the error values have known, relatively small, bounded magnitudes. Unfortunately, such bounds are typically unavailable in practice, so bounded error approaches are not widely applied. More generally, only estimates of the expected error values can be made, as will be discussed subsequently.
The measurement of a signal is provided by a measuring device. A measuring device as defined herein may be, but is not limited to, any physical device that interacts with a physical system and provides information that can be converted into an estimate comprised of a nominal estimate of the state of the system and an estimate of the error associated with that nominal state estimate. A measuring device as defined herein includes any device that emits a signal and measures the change of the signal upon its return, a device that measures a signal that is naturally produced by a physical process, or any device that measures a signal that is produced by a man made process.
Data Fusion For Signals Containing Mean and Covariance Information:
In one of the most common formulations of the data fusion problem, each estimate is represented as, or can be converted to, a pair comprising a state vector (often referred to as the mean) a and an error matrix A, denoted {a,A}. The state vector a is a (column) vector composed of m elements in which element a(i) corresponds to a variable, such as size or temperature, describing the state of a system of interest. The error matrix A is a matrix having m rows and m columns in which the element A(i,j), for any choice of i and j between 1and m, is related to the expected value of the product of the errors associated with the values stored in elements a(i) and a(j). If the value of element A(i,j) is precisely the expected value of the product of the errors associated with the values stored in elements a(i) and a(j), for any choice of i and j between 1 and m, then A is referred to as the error covariance of the estimated state vector a.
The error matrix A is often referred to as a covariance matrix according to a general definition of a covariance matrix as being a symmetric matrix with nonnegative eigenvalues, but A is not in general the true error covariance T associated with the state estimate a because T is usually unknown. The standard practice is to choose A large enough that it can be assumed to be of the form A=T+E, where E is an unknown covariance matrix representing the overestimated components of A. An overestimated covariance matrix is said to be "conservative" because it suggests that the state estimate is less accurate than it actually is. This is preferred to an underestimated covariance that suggests that the state estimate is more accurate than it actually is. For example, an underestimated covariance could lead a chemical plant operator to believe that the state of a chemical reaction is comfortably within safe operating bounds when in fact the magnitude of the errors in the state estimate are sufficiently large that the true state could easily be outside of the bounds.
The terms mean and covariance sometimes will be used hereafter as abbreviations for state vector and error matrix, respectively, in a manner consistent with colloquial usage in the fields of estimation, filtering, and data fusion.
The data fusion problem for mean and covariance estimates is exemplified by the case of two conservative estimates {a,A} and {b,B}, generated from different sensors, of the state of an autonomous vehicle. In order to steer the vehicle it is necessary to fuse the given estimates into a single estimate to be used by the steering mechanism. A trivial (though apparently never described in the literature) approach for fusing the two estimates would be to produce a fused estimate that consists only of the estimate having the "smaller" covariance matrix, in terms of some measure such as the trace or determinant, and disregard any information contained in the other estimate. In order to avoid having to disregard information from one of the estimates, it is necessary to have a means for generating a fused estimate that combines information from both given estimates and is still guaranteed to be conservative.
The Kalman Filler Update Equation:
The method that is most commonly used for fusing mean and covariance estimates is the Kalman update equation, which is the fundamental component of the well known Kalman filter. The Kalman update equation is known to generate an optimal conservative fused estimate {c,C} from given estimates {a,A} and {b,B} as long as the errors associated with a and b are not correlated. If the errors are correlated, however, then the Kalman estimate is not guaranteed to be conservative. An enhancement to the Kalman update equation has been developed for the case when the exact degree of correlation (defined by a cross covariance matrix) is known, but it cannot be applied in the general case when the degree of correlation is unknown.
A common approach for addressing the problem of fusing correlated estimates is to use the Kalman update equation, knowing that it may yield an underestimated covariance matrix, and then enlarge the resulting covariance matrix by some ad hoc heuristic method so that it can be assumed conservative. Unfortunately, there is no general prior art method for fusing information from two or more conservative estimates to generate an improved estimate that is guaranteed to be conservative. In many problem areas, such as in large decentralized data fusion networks, the problem is most acute because no amount of heuristic tweaking can avoid the limitations of the Kalman update algorithrn. This is of enormous consequence because of the general trend toward decentralization in complex military and industrial systems.
Decentralized Data Fusion Systems:
A decentralized date fusion system is a collection of processing nodes, connected by communication links, in which none of the nodes has knowledge about the overall network topology. Each node performs a specific computing task using information from nodes with which it is linked, but there is no "central" node that controls the network. There are many attractive properties of such decentralized systems, including:
Decentralized systems are reliable in the sense that the loss of a subset of nodes and/or links does not necessarily prevent the rest of the system from functioning. In a centralized system, however, the failure of a common communication manager or of a centralized controller can result in immediate catastrophic failure of the system. PA1 Decentralized systems are flexible in the sense that nodes can be added or deleted by making only local changes to the network. For example, the addition of a node simply involves the establishment of links to one or more nodes in the network. In a centralized system, however, the addition of a new node may change the topology in such a way as to require massive changes to the overall control and communications structure. PA1 1. The photo reconnaissance node transmits information about potentially important features. PA1 2. The troop position estimation node interprets one of the features as possibly being a mobilizing tank battalion at position x. A low confidence hypothesis is then transmitted suggesting that a tank battalion may have mobilized at position x. PA1 3. The information that a tank battalion may have mobilized at position x leads the reconnaissance photo node to interpret the same feature as confirming evidence for the hypothesis. The node then transmits high confidence information that a feature at position x represents a mobilizing tank battalion. PA1 4. The troop position node receives information from the reconnaissance photo node that a mobilizing tank battalion has been identified with high confidence. PA1 1. A reaction vessel is fitted with a variety of sensors including a pressure gauge. PA1 2. Because the bulk temperature of the reaction cannot be measured directly, a node is added that uses pressure information from the pressure node, combined with a model for the reaction, to estimate temperature. PA1 3. A safety monitoring node is added to the system that uses information from the temperature and pressure nodes to determine whether the reaction is proceeding normally. PA1 (1) means for obtaining measurement estimates relating to the state of a physical system and to the error covariance of that measurement; PA1 (2) means for transforming a set of estimates to a common coordinate system; PA1 (3) means for determining (implicitly or explicitly) a weighting factor for each of a plurality of mean and covariance estimates in inverse form such that the sum of the weighting factors is one; PA1 (4) means for computing (implicitly or explicitly) a weighted sum of a plurality of mean and covariance estimates in inverse form and transmitting a signal derived from the sum; and optionally, PA1 (5) means for physically responding based on the fused signal.
The most important class of decentralized networks involves nodes associated with sensors or other information sources. Information from distributed sources propagates through the network so that each node obtains the data relevant to its own processing task. In a battle management application, for example, one node might be associated with the acquisition of information from reconnaissance photos, another with ground-based reports of troop movements, and another with the monitoring of communications transmissions. Information from these nodes might then be transmitted to a node that estimates the position and movement of enemy troops. The information from this node might then be transmitted back to the reconnaissance photo node, which would use the estimated positions of the troops to aid in the automated interpretation of ambiguous features in satellite photos.
The most serious problem arising in decentralized data fusion networks is the effect of correlated (redundant) information. Specifically, pieces of information from multiple sources cannot be combined using the Kalman update algorithm unless they are uncorrelated or have a known degree of correlation. In the battle management example described above, the effect of correlated information can be seen in the following scenario:
The obvious problem is that the two nodes are exchanging redundant pieces of information but are treating them as independent pieces of evidence mounting in support of the hypothesis that a tank battalion has mobilized. A similar situation can arise in a decentralized monitoring system for a chemical process:
The added warning node will always be using redundant information from the pressure gauge. Thus if the estimates of pressure and temperature are treated as uncorrelated, then the fact that their relationship is always what is predicted by the model might lead to over confidence in the stability of the system.
Methods for avoiding the potentially disastrous effects of redundant information in decentralized networks has been a significant research area for several years. A devastating blow to the field came from Oxford researcher Simukai Utete who proved that in a general decentralized network it is impossible to avoid the deleterious effects of correlated estimates using the Kalman update algorithm. This proof seemed to pessimistically settle most of the open questions about the usefulness of decentralized estimation systems. However, her proof is based on the Kalman update requirement for strict knowledge of the degrees of correlation among estimates to be fused. If a different data fusion method is used that does not require any assumptions that estimates to be fused are uncorrelated, then the promise of general decentralized estimation can be realized. The present invention represents such a method.